526F - Pudding Monsters - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define ssize(x) (int)(x).size()

template <class T, class F> struct RMQ {
    vector<vector<T>> dp;
    F op;
    RMQ() {}
    RMQ(const vector<T>& a, F a_op) : dp(1, a), op(a_op) {
        for (int i = 0; (2 << i) <= ssize(a); i++) {
            dp.emplace_back(ssize(a) - (2 << i) + 1);
            transform(begin(dp[i]), end(dp[i]) - (1 << i), begin(dp[i]) + (1 << i), begin(dp[i + 1]), op);
        }
    }
    inline T query(int le, int ri) {
        assert(0 <= le && le < ri && ri <= ssize(dp[0]));
        int lg = __lg(ri - le);
        return op(dp[lg][le], dp[lg][ri - (1 << lg)]);
    }
};

struct perm_tree {
    vector<bool> is_join;
    vector<int> mn_idx, mn_val, len;
    int root;
    vector<vector<int>> adj;
    bool touches(int u, int v) {
        return mn_val[u] == mn_val[v] + len[v] || mn_val[v] == mn_val[u] + len[u];
    }
    int allocate(bool join, int mn_i, int mn_v, int ln, const vector<int>& ch) {
        int u = ssize(adj);
        is_join.push_back(join);
        mn_idx.push_back(mn_i);
        mn_val.push_back(mn_v);
        len.push_back(ln);
        adj.push_back(ch);
        return u;
    }
    perm_tree(const vector<int>& a) {
        int n = ssize(a);
        vector<int> mn_i(n), mx_i(n);
        {
            vector<int> a_inv(n, -1);
            for (int i = 0; i < n; i++) {
                assert(0 <= a[i] && a[i] < n && a_inv[a[i]] == -1);
                a_inv[a[i]] = i;
            }
            RMQ min_idx(a_inv, [](int x, int y) {return min(x, y);});
            RMQ max_idx(a_inv, [](int x, int y) {return max(x, y);});
            for (int i = 1; i < n; i++) {
                auto [le, ri] = minmax(a[i - 1], a[i]);
                mn_i[i] = min_idx.query(le, ri + 1);
                mx_i[i] = max_idx.query(le, ri + 1);
            }
        }
        RMQ min_value(a, [](int x, int y) {return min(x, y);});
        for (int i = 0; i < n; i++) allocate(1, i, a[i], 1, {});
        vector<int> st;
        vector<array<int, 3>> fail;
        for (int i = 0; i < n; i++) {
            int u = i;
            while (!empty(st)) {
                int v = st.back();
                if (is_join[v] && !empty(adj[v]) && touches(adj[v].back(), u)) {
                    mn_idx[v] = min(mn_idx[v], mn_idx[u]);
                    mn_val[v] = min(mn_val[v], mn_val[u]);
                    len[v] += len[u];
                    adj[v].push_back(u);
                    u = v;
                    st.pop_back();
                    continue;
                }
                if (touches(u, v)) {
                    assert(mn_idx[v] < mn_idx[u]);
                    assert(mn_idx[v] + len[v] == mn_idx[u]);
                    u = allocate(1, mn_idx[v], min(mn_val[u], mn_val[v]), len[u] + len[v], {v, u});
                    st.pop_back();
                    continue;
                }
                int idx = ssize(st) - 1;
                assert(mn_idx[v] < mn_idx[u]);
                assert(mn_idx[v] + len[v] == mn_idx[u]);
                int le = min(mn_idx[v], mn_i[mn_idx[u]]);
                assert(mn_idx[u] + len[u] - 1 == i);
                int ri = max(i, mx_i[mn_idx[u]]);
                assert(ri - le + 1 > len[u] + len[v]);//initially there's some gap between them, else we'd have hit case 2
                assert(!empty(st));
                while(!empty(fail) && fail.back()[0] >= idx) fail.pop_back();
                while (ri == i && le != mn_idx[st[idx]]) {
                    assert(!empty(fail));
                    assert(fail.back()[0] < idx);
                    idx = fail.back()[0];
                    le = min(le, fail.back()[1]);
                    ri = max(ri, fail.back()[2]);
                    fail.pop_back();
                }
                if (ri > i) {
                    assert(!empty(st));
                    fail.push_back({idx, le, ri});
                    break;
                }
                st.push_back(u);
                u = allocate(0, le, min_value.query(le, ri + 1), ri - le + 1, {begin(st) + idx, end(st)});
                st.resize(idx);
            }
            st.push_back(u);
        }
        assert(ssize(st) == 1);
        root = st[0];
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        int r, c;
        cin >> r >> c;
        r--,c--;
        a[r] = c;
    }
    perm_tree pt(a);
    queue<int> q;
    q.push(pt.root);
    long long res = 0;
    while(!empty(q)) {
        int u = q.front();
        q.pop();
        //cout << "range: " << pt.mn_val[u] << " " << pt.mn_val[u] + pt.len[u] - 1 << " join: " << pt.is_join[u] << " num childs: " << ssize(pt.adj[u]) << endl;
        if(empty(pt.adj[u])) res++;
        else if(pt.is_join[u]) res += 1LL * ssize(pt.adj[u]) * (ssize(pt.adj[u]) - 1) / 2;
        else res++;
        for(int v : pt.adj[u]) q.push(v);
    }
    cout << res << '\n';
    return 0;
}